It is well known that digital data transmitted over a communications channels is subject to signal impairments created by noise, distortion and fading, creating transmission errors. These types of errors can also occur when digital data is stored on devices, including magnetic media or solid-state memories that contain imperfections. This noise is critical in wireless communications where the noise can be extensive and the amount of power used in communication is limited. Typically, the noisy channel is characterized by the signal-to-noise ratio (SNR), which is a ratio of the signal energy over the noise energy in decibels. It is also possible to take the difference in transmission rates into account and define the SNR per bit when the efficiency of codes is compared with different code rates.
It is known that introducing a controlled amount of redundancy by coding in a selected message before a transmission over a communications channel corrects possible errors due to noise, as noted by Dr. Claude Shannon. In a noisy channel, the transmission rate is reduced to obtain accuracy. A limit, called the Shannon limit, shows the upper bound of the transmission rate for lossless communications in a noisy channel.
Block codes were first used in communications, but these block codes were not efficient when comparing to the Shannon limit. More efficient channel codes have been developed on the basis of trellis coding. A trellis encoder includes a Finite State Machine (FSM) and typically a signal mapper. The trellis is generated by the FSM, while code words are binary sequences that are one-to-one mappings of all distinct paths on the trellis by the signal mapper. When a special input sequence is transmitted, the path corresponding to this input sequence is found on the trellis, and the code word generated by the signal mapper. On the decoding side, a maximum likelihood (ML) decoder as a Viterbi decoder or a Maximum a Posteriori (MAP) decoder converts the received code words into the input sequence.
One important parameter of the Finite State Machine is the memory length m that decides the trellis. The most widely used trellis codes include convolutional codes and turbo codes, as noted in many teachings, including the IEEE technical paper entitled, “Modulation Encoding For Linear Gaussian Channels,” IEEE Transactions on Information Theory, Volume 44, No. 6, October 1998, the disclosure which is hereby incorporated by reference in its entirety.
Other examples of trellis coding, the use of convolutional codes, and convolutional encoders are disclosed in U.S. Pat. Nos. 5,706,312; 6,108,374; 6,215,827 assigned to Lucent Technologies; and 6,347,122 assigned to Agere Systems, the disclosures which are hereby incorporated by reference in their entirety.
Among the different convolutional codes, it is known that some exhibit a characteristic behavior known as catastrophic error propagation. In other words, in catastrophic codes, a finite sequence of errors in the receive signal sequence could result in an infinite sequence of decoding errors. This happens when there is a sequence of input such that the corresponding state sequence starts and ends at the same state while the output code sequence consists of all zeros. An example is the input sequence which consists of all ones, while generator polynomials have an even number of ones. Thus, many signal errors in transmission could occur with this type of coding.